package Offer;

import java.math.BigInteger; //需要手动导包 大整数类
import java.util.Arrays;

public class T14II_cuttingRope {
//    方法一：动态规划
    /*
        这道题给定一个大于 1 的正整数 n，要求将 n 拆分成至少两个正整数的和，并使这些正整数的乘积最大化，返回最大乘积。
        令 x 是拆分出的第一个正整数，则剩下的部分是 n-x，n-x 可以不继续拆分，或者继续拆分成至少两个正整数的和。
        由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
        创建数组 dp，其中dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
        特别地，0 不是正整数，11 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。
        当  i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（ 1≤j<i），则有以下两种方案：
        将  i 拆分成 j  和 i-j  的和，且 i-j  不再拆分成多个正整数，此时的乘积是  j×(i−j)；
        将  i 拆分成  j 和 i-j  的和，且 i-j  继续拆分成多个正整数，此时的乘积是  j×dp[i−j]。
        因此，当  j 固定时，有  dp[i]=max(j×(i−j),j×dp[i−j])。由于 jj 的取值范围是 1到 i-1 ，需要遍历所有的 j 得到
        dp[i] 的最大值，因此可以得到状态转移方程如下：
        dp[i]={max(j×(i−j),j×dp[i−j])} 最终得到dp[n] 的值即为将正整数n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
* */
//    相比于剪绳子I，本题会存在数值范围太大溢出的问题，所以可以用BigInteger来解决
    public int cuttingRope(int n) {
        BigInteger[] dp = new BigInteger[n + 1];  //dp[i]表示整数i拆分成至少2个数之后，得到的最大乘积
        // 由于0和1都不能拆，所以dp[0]和dp[1]都是0，而其他dp值还没求出来之前的初始值也是0
        Arrays.fill(dp, BigInteger.valueOf(0));
        BigInteger curMax;

        for (int i = 2; i <= n; i++) {
            curMax = BigInteger.valueOf(0);
            for (int j = 1; j < i; j++) {
                curMax = curMax.max(BigInteger.valueOf(j * (i - j))). //取 curMax、j*dp[i-j]、j*(i-j)的最大值
                        max(dp[i - j].multiply(BigInteger.valueOf(j)));
            }
            dp[i] = curMax; //这里不能直接对dp[i]进行取余操作，会影响到后面max的大小比较
        }
        return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
    }


//    方法二: 数学
//    根据推导,当绳子被切分为长度为3的n段时,得到的乘积是最大的; 所以将绳子均分后,最后一段的长度只可能是0 1 2
//    令a=n/3,如果:
//     1) n%3==0  return 3^a
//     2) n%3==1  return 3^(a-1)* (2*2)   最后一段长度为1,说明前一段长度为3,而1*3 < 2*2,所以最后两段的长度为2的时候得到最大乘积
//     3) n%3==2  return (3^a) * 2        最后一段长度是2,直接乘上,不用拆了,拆成1 1 更少
//    注:使用BigInteger效率低了很多!
    public int cuttingRope_2(int n) { //已知 100 >= n >= 2
        if (n < 4) {
            return n - 1;
        }
//        BigInteger a = BigInteger.valueOf(n / 3);
//        BigInteger b = BigInteger.valueOf(n % 3);
        int a = n / 3;
        int b = n % 3;

        int ans;
        if (b == 0) {
            return BigInteger.valueOf(3).pow(a).mod(BigInteger.valueOf(1000000007)).intValue();
        } else if (b == 1) {
            return BigInteger.valueOf(3).pow(a-1).multiply(BigInteger.valueOf(4)).mod(BigInteger.valueOf(1000000007)).intValue();
        } else {
            return BigInteger.valueOf(3).pow(a).multiply(BigInteger.valueOf(2)).mod(BigInteger.valueOf(1000000007)).intValue();
        }
    }


//   不使用BigInteger效率会好很多
    public int cuttingRope_3(int n) {
        if(n <= 3)
            return n - 1;

        int b = n % 3, p = 1000000007;
        long ret = 1;
        int lineNums=n/3;           //线段被我们分成以3为大小的小线段个数

        // 求 3^lineNums
        for(int i=1;i<lineNums;i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。
            ret = 3*ret % p; //每次运算做取余操作,保证不会越界

        if(b == 0)
            return (int)(ret * 3 % p);   //刚好被3整数的，要算上前一段

        if(b == 1)
            return (int)(ret * 4 % p);   //被3整数余1的，要算上前一段
        return (int)(ret * 6 % p);       //被3整数余2的，要算上前一段
    }



}